package leetcode.递归回溯BFSDFS;

/**
 * N皇后ll DFS
 *
 * @author https://leetcode-cn.com/problems/n-queens/
 * @author https://mp.weixin.qq.com/s?__biz=MzIzMDc5Mjg4Mw==&mid=100000465&idx=1&sn=949cecc27bcbe6a62eb3c6efa2dedf72&chksm=68af490d5fd8c01bf423e8c33bc20995fa687d828f758c18ebc3c074ef627b12d16ef39baba0&scene=20#rd
 * <p>
 * 分析题目可知一旦某一行放置一个皇后了，那么这一行、左右对角线均不能存放任何皇后了
 * <p>
 * 因此需要知道当前皇后所在的位置，以及左右对角线如何计算，还要状态数组存放之前操作的结果
 */
public class Test52N皇后II {

    public static void main(String[] args) {
//        System.out.println(totalNQueens(4));
        System.out.println(1 << 4);
    }

    private static int count = 0;

    public static int totalNQueens(int n) {
        if (n < 1)
            return 0;
        dfs(0, 0, 0, 0, n);
        return count;
    }

    private static void dfs(int row, int col, int pie, int na, int n) {
        if (row >= n) {
            count++;
            return;
        }
        /**
         * 将所有能放置 Q 的位置由 0 变成 1，以便进行后续的位遍历
         *
         * ~(col | ld | rd)这里的三个变量分别代表了列以及两个斜线的放置情况。
         *
         * (1 << n) - 1 这个语句实际上生成了n个1.这里的1表示可以放置皇后（其实就是初始化了n个1）
         *
         *
         */
        int bit = (~(col | pie | na)) & ((1 << n) - 1);
        while (bit > 0) {//遍历所有空位
            int p = bit & -bit; // 保留最后一个 1
            /**
             col | p 表示 p 位被占用
             (pie | p ) << 1 ,表示pie往斜左方移一位 被占用
             (na | p) >> 1,表示na往斜右方移一位 被占用
             **/
            dfs(row + 1, col | p, (pie | p) << 1, (na | p) >> 1, n);
            bit &= (bit - 1); // 将最后一个 1变成 0
        }
    }


//    /**
//     * n 皇后，行、列数都是 n
//     * 设 rowIndex 表示行号，i 表示列号
//     * 左对角线计算公式：rowIndex + i
//     * 右对角线计算公式：rowIndex - i + N - 1
//     */
//
//    public static int totalNQueens(int n) {
//        boolean[] column = new boolean[n];
//        // 2*n个斜对角线
//        boolean[] leftDiagonal = new boolean[2 * n];
//        boolean[] rightDiagonal = new boolean[2 * n];
//        List<List<String>> result = new ArrayList<>();
//        if (n == 0)
//            return 0;
//        backtrack(result, new ArrayList<>(), column, leftDiagonal, rightDiagonal, 0);
//        return result.size();
//    }
//
//    private static void backtrack(List<List<String>> result, List<String> current,
//                           boolean[] column, boolean[] leftDiagonal,
//                           boolean[] rightDiagonal, int rowIndex) {
//        int N = column.length;
//        if (rowIndex == N) {
//            result.add(new ArrayList<>(current));
//            return;
//        }
//
//        for (int i = 0; i < N; i++) {
//            // 发现本列、某一左右对角线不能存放皇后了，就需要让 i++ ，找一个新的地方再判断
//            if (column[i] || leftDiagonal[rowIndex + i] || rightDiagonal[rowIndex - i + N - 1]) {
//                continue;
//            }
//
//            // init一个长度为 n 的一维数组，里面初始化为 '.'
//            char[] charArray = new char[N];
//            Arrays.fill(charArray, '.');
//            // 当前位置允许放置皇后，就存入一个“Q”
//            charArray[i] = 'Q';
//            String stringArray = new String(charArray);
//            current.add(stringArray);
//            // 只要当前的行放下一个皇后,这一列、对角、反对角线都不能再放了.标记完后进行回溯
//            column[i] = true;
//            leftDiagonal[rowIndex + i] = true;
//            rightDiagonal[rowIndex - i + N - 1] = true;
//
//            backtrack(result, current, column, leftDiagonal, rightDiagonal, rowIndex + 1);
//
//            //reset 不影响回溯的下个目标
//            current.remove(current.size() - 1);
//            charArray[i] = '.';
//            column[i] = false;
//            leftDiagonal[rowIndex + i] = false;
//            rightDiagonal[rowIndex - i + N - 1] = false;
//        }
//    }

}
